/*
@author: ZZH
@date: 2021-11-05
@time: 14:22:11
@info: 红黑树指针域操作实现
*/
#include "RB-Tree-Base.h"
#include "RB-Tree-OP.h"

typedef enum
{
    RBT_Idle,//初始状态,决定遍历方向
    RBT_EnterLeft,//进入左子树
    RBT_VisitLeft,//已经访问过左子树
    RBT_EnterRight,//进入右子树
    RBT_VisitRight//已经访问过右子树
}RBT_State_t;

//节点左旋操作
static void LeftSpin(pRBTree_t tree, pRBTreeNode_t node)
{
    pRBTreeNode_t right = node->right; //获取node的右子树
    if (right == NULL)
        return;

    //处理右子树的左子树，双向连接
    node->right = right->left; //node右子树的左子树现在是node的右子树
    if (right->left)
        RBT_PARENT(right->left) = node; //node右子树的左子树的父节点现在是node

    //处理右子树和node父节点的亲缘关系
    RBT_PARENT(right) = RBT_PARENT(node); //右子树的父节点换成node的父节点
    if (RBT_IS_NIL(RBT_PARENT(right)))    //如果node曾经的父节点为空,说明node之前就是根节点,因此左旋之后right就是新的根节点
        tree->root = right;               //将树的根节点设为right
    else if (node == RBT_BROTHER_L(node)) //如果node原本是左子树
        RBT_BROTHER_L(node) = right;      //right顶替node原本的位置成为其父节点的左子树
    else if (node == RBT_BROTHER_R(node)) //逻辑同上,只不过判断的是右子树
        RBT_BROTHER_R(node) = right;      //逻辑同上,只不过是右子树

    //处理node，主要是和之前的右子树的关系
    right->left = node;   //左旋之后,node为原本右子树的左子树
    node->parent = right; //因此现在node的父节点为原本的右子树
}

//节点右旋操作
static void RightSpin(pRBTree_t tree, pRBTreeNode_t node)
{
    pRBTreeNode_t left = node->left; //获取左子树
    if (left == NULL)
        return;

    //处理左子树的右子树，双向连接
    node->left = left->right;
    if (left->right)
        RBT_PARENT(left->right) = node;

    //处理左子树和node父节点的亲缘关系
    RBT_PARENT(left) = RBT_PARENT(node);
    if (RBT_IS_NIL(RBT_PARENT(left)))
        tree->root = left;
    else if (node == RBT_BROTHER_L(node))
        RBT_BROTHER_L(node) = left;
    else if (node == RBT_BROTHER_R(node))
        RBT_BROTHER_R(node) = left;

    //处理node和之前的左子树的关系
    left->right = node;
    node->parent = left;
}

static uint32_t __numObj;
//用于计算节点数量的回调函数
static void __RBT_Count(pRBTree_t tree, pRBTreeNode_t node, uint32_t level)
{
    __numObj += (node != NULL);
}

//计算红黑树内节点数量
uint32_t RBT_CountObjects(pRBTree_t tree)
{
    __numObj = 0;
    __RBT_Visit visit_fn = tree->visit;
    tree->visit = __RBT_Count;
    //遍历访问所有节点，包括NIL，但NIL并不计入总数，三种遍历在计数上无差异，这里随便使用先序遍历
    RBT_FirstOrderFsm(tree);
    tree->visit = visit_fn;
    return __numObj;
}

static uint32_t __height;
//用于计算树高度的回调函数
static void __RBT_Height(pRBTree_t tree, pRBTreeNode_t node, uint32_t level)
{
    __height = level > __height ? level : __height;
}

//计算红黑树高度
uint32_t RBT_Height(pRBTree_t tree)
{
    __height = 0;
    __RBT_Visit visit_fn = tree->visit;
    tree->visit = __RBT_Height;
    //遍历访问所有节点，包括NIL，但NIL并不计入总数，三种遍历在计算高度上无差异，这里随便使用先序遍历
    RBT_FirstOrderFsm(tree);
    tree->visit = visit_fn;
    return __height;
}

//先序遍历红黑树，递归形式，并提供当前的递归层数
void _RBT_FirstOrderRecursive(pRBTree_t tree, pRBTreeNode_t root, uint32_t level)
{
    if (tree->visit == NULL || tree == NULL || RBT_IS_NIL(root))
        return;

    tree->visit(tree, root, level);
    _RBT_FirstOrderRecursive(tree, root->left, level + 1);
    _RBT_FirstOrderRecursive(tree, root->right, level + 1);
}

//中序遍历红黑树，递归形式，并提供当前的递归层数
void _RBT_MiddleOrderRecursive(pRBTree_t tree, pRBTreeNode_t root, uint32_t level)
{
    if (tree->visit == NULL || tree == NULL || RBT_IS_NIL(root))
        return;

    _RBT_MiddleOrderRecursive(tree, root->left, level + 1);
    tree->visit(tree, root, level);
    _RBT_MiddleOrderRecursive(tree, root->right, level + 1);
}

//后序遍历红黑树，递归形式，并提供当前的递归层数
void _RBT_LastOrderRecursive(pRBTree_t tree, pRBTreeNode_t root, uint32_t level)
{
    if (tree->visit == NULL || tree == NULL || RBT_IS_NIL(root))
        return;

    _RBT_LastOrderRecursive(tree, root->left, level + 1);
    _RBT_LastOrderRecursive(tree, root->right, level + 1);
    tree->visit(tree, root, level);
}

//静态创建红黑树，也就是红黑树结构本身为静态结构体，节点依然是动态创建出来的，其他同上
void __RBT_CreateStatic(pRBTree_t tree)
{
    tree->compare = NULL;
    tree->free = NULL;
    tree->visit = NULL;
    tree->root = NULL;
    tree->copy = NULL;
}

uint8_t __RBT_InsertNode(pRBTree_t tree, pRBTreeNode_t node, void* key)
{
    if (tree->compare == NULL || tree == NULL || node == NULL || key == NULL)
        return 0;//插入失败

    pRBTreeNode_t root = tree->root;//获取根节点
    pRBTreeNode_t pInsert = NULL;

    //新节点必然符合以下三条
    node->left = NULL;
    node->right = NULL;
    node->color = RBT_Red;//插入的节点总为红色

    //根据键的大小找到合适的插入位置
    while (!RBT_IS_NIL(root))
    {
        pInsert = root;
        RBT_CompareResult_t res = tree->compare(root, key);

        switch (res)
        {
            case RBT_Equal:
                if (tree->copy == NULL)
                    return 0;

                tree->copy(root, node);//更新插入位置的键值对
                tree->free(node);
                return 2;

            case RBT_Small:
                root = root->left;
                break;

            case RBT_Big:
                root = root->right;
                break;
        }
    }

    RBT_PARENT(node) = pInsert;//插入位置节点成为新节点的父节点

    if (RBT_IS_NIL(pInsert))//插入位置为空,说明树为空,插入到根节点位置
        tree->root = node;
    else if (tree->compare(pInsert, key) == RBT_Small)//插入的节点key小于插入位置的key
        pInsert->left = node;//插入为左子树
    else
        pInsert->right = node;//插入为右子树

    //插入完成,接下来对插入后的树进行调整,使其满足红黑树性质
    //由于红节点下方不可再有红节点,这里存在三种情况,后两种情况实际上各自还可再细分为两种,共五种实际情况
    while (RBT_GET_COLOR(RBT_PARENT(node)) == RBT_Red)
    {
        pRBTreeNode_t parNode = RBT_PARENT(node), uncNode = RBT_GET_UNCLE(node);
        /*
        1.父节点为红色,且叔叔节点也是红色(黑色的祖父节点下挂两个红节点)
        处理方法:
            (01) 将 父节点 设为黑色
            (02) 将 叔叔节点 设为黑色
            (03) 将 祖父节点 设为 红色
            (04) 将 祖父节点 设为 当前节点 (红色节点) 之后继续对 当前节点 进行操作
        */
        if (RBT_GET_COLOR(uncNode) == RBT_Red)//叔叔节点为红
        {
            parNode->color = RBT_Black;             //(01)
            uncNode->color = RBT_Black;             //(02)
            RBT_PARENT(parNode)->color = RBT_Red;   //(03)
            node = RBT_PARENT(parNode);             //(04)
            continue;
        }
        /*
        2.叔叔是黑色,且父节点是祖父节点的左孩子
        处理方法:
            分 2.1 和 2.2 两种情况分别处理
        */
        else if (parNode == RBT_BROTHER_L(parNode))//node的父节点是祖父节点的左孩子
        {
            /*
            2.1.叔叔是黑色,并且当前节点是父节点的右孩子
            这里的操作本质上是将2.1的情况转化为2.2的情况,2.2的操作才是真正化解情况2的操作
            处理方法:
                (01) 以 父节点 为支点进行左旋
                (02) 重设 父节点 和 当前节点,转化为2.2情况
            */
            if (node == RBT_BROTHER_R(node))//
            {
                LeftSpin(tree, parNode);   //(01)
                SWAP(node, parNode);       //(02)
            }
            /*
            2.2.叔叔是黑色,并且当前节点是父节点的左孩子,此处无需判断,因为node只有左右两种可能性,而2.1的存在保证了运行到这里一定是左子树
            处理方法:
                (01) 将 父节点 设为黑色
                (02) 将 祖父节点 设为红色
                (03) 以 祖父节点 为中心右旋
            */
            parNode->color = RBT_Black;            //(01)    
            RBT_PARENT(parNode)->color = RBT_Red;  //(02)
            RightSpin(tree, RBT_PARENT(parNode));  //(03)
        }
        /*
        3.叔叔是黑色,且父节点是祖父节点的右孩子
        处理方法:
            分 3.1 和 3.2 两种情况分别处理
        */
        else if (parNode == RBT_BROTHER_R(parNode))//这里处理同上,只是左右关系颠倒而已
        {
            /*
            3.1.叔叔是黑色,并且当前节点是父节点的左孩子
            这里的操作本质上是将3.1的情况转化为3.2的情况,3.2的操作才是真正化解情况3的操作
            处理方法:
                (01) 以 父节点 为支点进行右旋
                (02) 重设 父节点 和 当前节点,转化为3.2情况
            */
            if (node == RBT_BROTHER_L(node))//
            {
                RightSpin(tree, parNode);   //(01)
                SWAP(node, parNode);        //(02)
            }
            /*
            3.2.叔叔是黑色,并且当前节点是父节点的左孩子,此处无需判断,因为node只有左右两种可能性,而3.1的存在保证了运行到这里一定是右子树
            处理方法:
                (01) 将 父节点 设为黑色
                (02) 将 祖父节点 设为红色
                (03) 以 祖父节点 为支点左旋
            */
            parNode->color = RBT_Black;             //(01)
            RBT_PARENT(parNode)->color = RBT_Red;   //(02)
            LeftSpin(tree, RBT_PARENT(parNode));    //(03)
        }
    }
    tree->root->color = RBT_Black;//根节点必须为黑
    return 1;
}

//删除节点，此接口应当在具体的实现文件内调用
uint8_t __RBT_DeleteNode(pRBTree_t tree, pRBTreeNode_t node)
{
    if (RBT_IS_NIL(node) || tree->free == NULL)//需要删除的节点必须存在
        return 0;

    //实际要删除的节点
    pRBTreeNode_t ntd = (RBT_IS_NIL(node->left) || RBT_IS_NIL(node->right)) ? node : __RBT_Next(node);
    //替代节点,也就是实际删除节点的子节点
    pRBTreeNode_t child = RBT_IS_NIL(ntd->left) ? ntd->right : ntd->left;

    if (child)
        RBT_PARENT(child) = RBT_PARENT(ntd);

    if (RBT_IS_NIL(RBT_PARENT(ntd)))//删掉的是根节点
        tree->root = child;
    else if (ntd == RBT_BROTHER_L(ntd))//删掉左侧节点,重新链接左侧指针
        RBT_BROTHER_L(ntd) = child;
    else//同上,右侧
        RBT_BROTHER_R(ntd) = child;

    if (ntd != node)//如果这两个不等,说明删掉的是双子非空节点,实际删掉的是后继节点,所以把后继节点赋值给删掉的节点
        tree->copy(node, ntd);

    //节点删除完成,开始修复树
    if (RBT_GET_COLOR(ntd) == RBT_Black)
    {
        pRBTreeNode_t parNode = RBT_PARENT(ntd);
        //代替节点若不为黑,或为黑且是根节点,则无需处理,此处只处理为黑但不是根节点的情况,这种情况可分为四类,左右方向不同可细分为八类
        while (child != tree->root && RBT_GET_COLOR(child) == RBT_Black)
        {
            if (child == parNode->left)//当前节点为左侧节点
            {
                pRBTreeNode_t broNode = parNode->right;//兄弟节点就在右侧
                /*
                1.兄弟节点为红
                这里的处理是将1情况转换为2
                处理方法:
                    (01) 将 兄弟节点 设为黑色
                    (02) 将 父节点 设为红色
                    (03) 以 父节点 为支点左旋
                    (04) 重新设置 兄弟节点
                */
                if (RBT_GET_COLOR(broNode) == RBT_Red)//兄弟节点为红色
                {
                    broNode->color = RBT_Black;     //(01)
                    parNode->color = RBT_Red;       //(02)
                    LeftSpin(tree, parNode);        //(03)
                    broNode = parNode->right;       //(04)
                }

                /*
                2.兄弟节点为黑, 兄弟节点的子节点都为黑
                处理方法:
                    (01) 将 兄弟节点 设为红色
                    (02) 将 父节点 设为 代替节点
                */
                if (RBT_GET_COLOR(broNode->right) == RBT_Black && RBT_GET_COLOR(broNode->left) == RBT_Black)//兄弟为黑,兄弟的双孩子为黑
                {
                    broNode->color = RBT_Red; //(01)
                    child = parNode;          //(02)
                    parNode = RBT_PARENT(child);
                }
                else
                {
                    /*
                    3.兄弟节点为黑；兄弟节点的左孩子为红，右孩子为黑
                    处理方法:
                        (01) 将 兄弟节点的左孩子 设为 黑色
                        (02) 将 兄弟节点 设为 红色
                        (03) 以 兄弟节点 为支点进行右旋
                        (04) 重新设置 兄弟节点
                    */
                    if (RBT_GET_COLOR(broNode->right) == RBT_Black)
                    {
                        broNode->left->color = RBT_Black;   //(01)
                        broNode->color = RBT_Red;           //(02)
                        RightSpin(tree, broNode);           //(03)
                        broNode = parNode->right;           //(04)
                    }
                    /*
                    4.兄弟节点为黑；兄弟节点的右孩子为红，兄弟节点的左孩子任意颜色
                    处理方法:
                        (01) 将 父节点颜色 赋值给 兄弟节点
                        (02) 将 父节点设为 黑色
                        (03) 将 兄弟节点的右孩子 设为 黑色
                        (04) 以 父节点 为支点进行左旋。
                        (05) 设置 替代节点 为 根节点
                    */
                    broNode->color = parNode->color;    //(01)
                    parNode->color = RBT_Black;         //(02)
                    broNode->right->color = RBT_Black;  //(03)
                    LeftSpin(tree, parNode);            //(04)
                    child = tree->root;                 //(05)
                    break;
                }
            }
            else//左右交换,当前节点为右侧节点
            {
                pRBTreeNode_t broNode = parNode->left;//兄弟节点就在左侧
                /*
                5(1).兄弟节点为红
                这里的处理是将5(1)情况转换为6(2)
                处理方法:
                    (01) 将 兄弟节点 设为黑色
                    (02) 将 父节点 设为红色
                    (03) 以 父节点 为支点右旋
                    (04) 重新设置 兄弟节点
                */
                if (RBT_GET_COLOR(broNode) == RBT_Red)
                {
                    broNode->color = RBT_Black;     //(01)
                    parNode->color = RBT_Red;       //(02)
                    RightSpin(tree, parNode);       //(03)
                    broNode = parNode->left;        //(04)
                }

                /*
                6(2).兄弟节点为黑, 兄弟节点的子节点都为黑
                处理方法:
                    (01) 将 兄弟节点 设为红色
                    (02) 将 父节点 设为 代替节点
                */
                if (RBT_GET_COLOR(broNode->right) == RBT_Black && RBT_GET_COLOR(broNode->left) == RBT_Black)//兄弟为黑,兄弟的双孩子为黑
                {
                    broNode->color = RBT_Red;   //(01)
                    child = parNode;            //(02)
                    parNode = RBT_PARENT(child);
                }
                else
                {
                    /*
                    7(3).兄弟节点为黑；兄弟节点的右孩子为红，左孩子为黑
                    这里的处理是将7(3)情况转换为8(4)
                    处理方法:
                        (01) 将 兄弟节点的右孩子 设为 黑色
                        (02) 将 兄弟节点 设为 红色
                        (03) 以 兄弟节点 为支点进行左旋
                        (04) 重新设置 兄弟节点
                    */
                    if (RBT_GET_COLOR(broNode->left) == RBT_Black)
                    {
                        broNode->right->color = RBT_Black;  //(01)
                        broNode->color = RBT_Red;           //(02)
                        LeftSpin(tree, broNode);            //(03)
                        broNode = parNode->left;            //(04)
                    }
                    /*
                    8(4).兄弟节点为黑；兄弟节点的左孩子为红，兄弟节点的右孩子任意颜色
                    处理方法:
                        (01) 将 父节点颜色 赋值给 兄弟节点
                        (02) 将 父节点设为 黑色
                        (03) 将 兄弟节点的左孩子 设为 黑色
                        (04) 以 父节点 为支点进行右旋。
                        (05) 设置 替代节点 为 根节点
                    */
                    broNode->color = parNode->color;     //(01)
                    parNode->color = RBT_Black;          //(02)
                    broNode->left->color = RBT_Black;    //(03)
                    RightSpin(tree, parNode);            //(04)
                    child = tree->root;                  //(05)
                    break;
                }
            }
        }
        if (child)
            child->color = RBT_Black;
    }

    tree->free(ntd);

    return 1;
}

pRBTreeNode_t __RBT_SearchNodeCond(pRBTree_t tree, void* key, RBT_CompareResult_t cond)
{
    if (tree == NULL || tree->compare == NULL || key == NULL)
        return NULL;

    if (cond == RBT_Big)
        cond = RBT_Small;
    else if (cond == RBT_Small)
        cond = RBT_Big;

    pRBTreeNode_t root = tree->root;
    while (!RBT_IS_NIL(root))
    {
        RBT_CompareResult_t res = tree->compare(root, key);
        if (res != cond)
            switch (res)
            {
                case RBT_Equal:
                    root = (cond == RBT_Small) ? root->right : root->left;
                    break;
                    
                case RBT_Small:
                    root = root->left;
                    break;

                case RBT_Big:
                    root = root->right;
                    break;
            }
        else
            return root;
    }

    return NULL;
}

/*
@brief 返回某节点后继节点
@param node 任意节点
@return node的后继节点
*/
pRBTreeNode_t __RBT_Next(pRBTreeNode_t node)
{
    if (node == NULL)
        return NULL;

    pRBTreeNode_t min = node->right;
    if (min)
    {
        while (!RBT_IS_NIL(min->left))
            min = min->left;
    }
    else
    {
        pRBTreeNode_t pNode = RBT_PARENT(node);
        while ((!RBT_IS_NIL(pNode)) && node == pNode->right)
        {
            node = RBT_PARENT(node);
            pNode = RBT_PARENT(node);
        }
        min = pNode;
    }

    return min;
}

//先序遍历红黑树,外部可调用但不推荐，状态机实现O(1)空间复杂度
void _RBT_FirstOrderFsm(pRBTree_t tree, pRBTreeNode_t root, uint32_t level)
{
    if (tree->visit == NULL || tree == NULL)
        return;

    pRBTreeNode_t node = root;
    RBT_State_t now = RBT_Idle;//初始空闲态

    while (node)
    {
        switch (now)
        {
            case RBT_Idle://初始情况
                tree->visit(tree, node, 0);//先访问根节点
                if (RBT_IS_NIL(node->left))//左子树为空,相当于已经处理完了左子树
                    now = RBT_VisitLeft;
                else
                {
                    now = RBT_EnterLeft;//进入左子树
                    node = node->left;
                    level++;
                }
                break;

            case RBT_EnterLeft://进入左子树的情况
                tree->visit(tree, node, level);//先访问当前节点
                if (RBT_IS_NIL(node->left))//左子树为空,那么就可以停止向左,返回父节点
                {
                    node = RBT_PARENT(node);
                    now = RBT_VisitLeft;
                    level--;
                }
                else//不为空,继续向左
                {
                    node = node->left;
                    level++;
                }
                break;

            case RBT_VisitLeft://已经处理过左子树的情况
                if (RBT_IS_NIL(node->right))
                    now = RBT_VisitRight;
                else
                {
                    node = node->right;
                    now = RBT_EnterRight;
                    level++;
                }
                break;

            case RBT_EnterRight://进入右子树的情况
                tree->visit(tree, node, level);//先访问当前节点
                if (RBT_IS_NIL(node->left))
                {
                    if (RBT_IS_NIL(node->right))
                    {
                        node = RBT_PARENT(node);
                        now = RBT_VisitRight;
                        level--;
                    }
                    else
                    {
                        node = node->right;
                        level++;
                    }
                }
                else
                {
                    node = node->left;
                    now = RBT_EnterLeft;
                    level++;
                }
                break;

            case RBT_VisitRight:
                if (node != root)
                {
                    now = node == RBT_PARENT(node)->left ? RBT_VisitLeft : RBT_VisitRight;
                    node = RBT_PARENT(node);
                }
                else
                    node = NULL;
                level--;
                break;
        }
    }
}

//中序遍历红黑树,外部可调用但不推荐，状态机实现O(1)空间复杂度
void _RBT_MiddleOrderFsm(pRBTree_t tree, pRBTreeNode_t root, uint32_t level)
{
    if (tree->visit == NULL || tree == NULL)
        return;

    pRBTreeNode_t node = root;
    RBT_State_t now = RBT_Idle;//初始空闲态

    while (node)
    {
        switch (now)
        {
            case RBT_Idle://初始情况
                if (RBT_IS_NIL(node->left))//左子树为空,相当于已经处理完了左子树
                    now = RBT_VisitLeft;
                else
                {
                    now = RBT_EnterLeft;//进入左子树
                    node = node->left;
                    level++;
                }
                break;

            case RBT_EnterLeft://进入左子树的情况
                if (RBT_IS_NIL(node->left))//左子树为空,那么就可以停止向左,返回父节点
                {
                    tree->visit(tree, node, level--);//访问当前节点
                    node = RBT_PARENT(node);
                    now = RBT_VisitLeft;
                }
                else//不为空,继续向左
                {
                    node = node->left;
                    level++;
                }
                break;

            case RBT_VisitLeft://已经处理过左子树的情况
                tree->visit(tree, node, level);//先访问当前节点
                if (RBT_IS_NIL(node->right))
                    now = RBT_VisitRight;
                else
                {
                    node = node->right;
                    now = RBT_EnterRight;
                    level++;
                }
                break;

            case RBT_EnterRight://进入右子树的情况
                if (RBT_IS_NIL(node->left))
                {
                    tree->visit(tree, node, level);//访问当前节点
                    if (RBT_IS_NIL(node->right))
                    {
                        node = RBT_PARENT(node);
                        now = RBT_VisitRight;
                        level--;
                    }
                    else
                    {
                        node = node->right;
                        level++;
                    }
                }
                else
                {
                    node = node->left;
                    now = RBT_EnterLeft;
                    level++;
                }
                break;

            case RBT_VisitRight:
                if (node != root)
                {
                    now = node == RBT_PARENT(node)->left ? RBT_VisitLeft : RBT_VisitRight;
                    node = RBT_PARENT(node);
                }
                else
                    node = NULL;
                level--;
                break;
        }
    }
}

//后序遍历红黑树,外部可调用但不推荐，状态机实现O(1)空间复杂度
void _RBT_LastOrderFsm(pRBTree_t tree, pRBTreeNode_t root, uint32_t level)
{
    if (tree->visit == NULL || tree == NULL)
        return;

    pRBTreeNode_t node = root;
    RBT_State_t now = RBT_Idle;//初始空闲态

    while (node)
    {
        switch (now)
        {
            case RBT_Idle://初始情况
                if (RBT_IS_NIL(node->left))//左子树为空,相当于已经处理完了左子树
                    now = RBT_VisitLeft;
                else
                {
                    now = RBT_EnterLeft;//进入左子树
                    node = node->left;
                    level++;
                }
                break;

            case RBT_EnterLeft://进入左子树的情况
                if (RBT_IS_NIL(node->left))//左子树为空,那么就可以停止向左,处理完当前节点后返回父节点
                {
                    tree->visit(tree, node, level--);
                    node = RBT_PARENT(node);
                    now = RBT_VisitLeft;
                }
                else//不为空,继续向左
                {
                    node = node->left;
                    level++;
                }
                break;

            case RBT_VisitLeft://已经处理过左子树的情况
                if (RBT_IS_NIL(node->right))
                    now = RBT_VisitRight;
                else
                {
                    node = node->right;
                    now = RBT_EnterRight;
                    level++;
                }
                break;

            case RBT_EnterRight://进入右子树的情况
                if (RBT_IS_NIL(node->left))
                {
                    if (RBT_IS_NIL(node->right))
                    {
                        tree->visit(tree, node, level--);
                        node = RBT_PARENT(node);
                        now = RBT_VisitRight;
                    }
                    else
                    {
                        node = node->right;
                        level++;
                    }
                }
                else
                {
                    node = node->left;
                    now = RBT_EnterLeft;
                    level++;
                }
                break;

            case RBT_VisitRight:
                tree->visit(tree, node, level--);
                if (node != root)
                {
                    now = node == RBT_PARENT(node)->left ? RBT_VisitLeft : RBT_VisitRight;
                    node = RBT_PARENT(node);
                }
                else
                    node = NULL;
                break;
        }
    }
}

static void RBT_VisitFree(pRBTree_t tree, pRBTreeNode_t node, uint32_t level)
{
    tree->free(node);
}

//清空红黑树全部子树，状态机实现
void RBT_Clear(pRBTree_t tree)
{
    if (tree == NULL)
        return;

    __RBT_Visit visit_fn = tree->visit;
    tree->visit = RBT_VisitFree;
    RBT_LastOrderFsm(tree);
    tree->visit = visit_fn;
    tree->root = NULL;
}
